#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int MAXN = 1e6 + 10;
const int MOD = 998244353;

ll f[MAXN][30];
int t;
void init() {
    for (int i = 0; i < 26; i++) {
        f[1][i] = f[2][i] = 1;
    }

    for (int i = 3; i <= 1e6; i++) {
        for (int j = 0; j < 26; j++) {
            for (int k = 0; k < 26; k++) {
                f[i][j] += f[i - 2][k];
            }
        }
    }
}
int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    init();
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        ll res = 0;
        bool flag = 0;
        for (int l = 0, r = n - 1; l <= r; l++, r--) {
            int idx = s[l] - 'A';
            for (int i = 0; i < idx; i++) res = (res + f[r - l + 1][i]) % MOD;
            if (l != r && s[l] <= s[r])
                flag = 1;
            else
                flag = 0;
            if (l == r || flag) res++;
        }
        cout << res << endl;
    }
    return 0;
}